package com.stefan.sort;

import java.util.Arrays;

/*
* 归并排序，分而之治，先分后和的思想
*
*  */
public class MergeSort {

    public void sort(int[] elements,int left,int right) {
        if (left < right) { //相等的时候只有一位数了
            int mid = (left + right)/2;
            sort(elements,left,mid);
            sort(elements,mid+1,right);
            //分完之后就是合并
            merge(elements,left,mid,right);
        }
    }
    public void merge(int[] element,int left,int mid,int right) {
        int[] temp = new int[element.length];
        int position = left;//表示当前temp数组元素的index
        int p1 = left; //左边的第一个位置
        int p2 = mid+1; //右边的第一个位置

        while (p1 <= mid && p2 <= right) {
            if (element[p1]<element[p2]) {
                temp[position] = element[p1];
                p1++;
                position++;
            } else {
                temp[position] = element[p2];
                p2 ++;
                position++;
            }
        }
        while (p1 <= mid) {
            temp[position] = element[p1];
            p1++;
            position++;
        }
        while (p2 <= right) {
            temp[position] = element[p2];
            p2++;
            position++;
        }
        for (int i = left; i <= right; i++) {
            element[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] data = {7,3,2,9,4,6,0,5,1,8};
        mergeSort.sort(data,0, data.length-1);
        System.out.println(Arrays.toString(data));
    }
}
